package lc20240623;

import java.util.PriorityQueue;
import java.util.Collections;

/**
  * @description 数据流
  * @author 不知名帅哥
  * @date 2024/6/23 14:53
  * @version 1.0
*/
class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 用于存储较小的一半元素的最大堆
    private PriorityQueue<Integer> minHeap; // 用于存储较大的一半元素的最小堆

    /** 初始化数据结构 */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    /** 添加一个数到数据结构中 */
    public void addNum(int num) {
        // 先把num加到最大堆
        maxHeap.offer(num);
        // 把最大堆的堆顶元素加到最小堆
        minHeap.offer(maxHeap.poll());

        // 如果最小堆的元素多于最大堆
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    /** 返回当前所有元素的中位数 */
    public double findMedian() {
        //如果是奇数个，maxHeap的长度大于minHeap。如果是偶数个，maxHeap的长度==minHeap的长度
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }


    public static void main(String[] args) {
        MedianFinder medianFinder=new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
    }
}
